/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Admin
 * Date: 2022-11-12
 * Time: 20:06
 */
public class Demo2{
    /**
     *	正数数组中的最小不可组成和
     *	输入：正数数组arr
     *	返回：正数数组中的最小不可组成和
     */
    public int getFirstUnFormedNum(int[] arr) {
        int max = 0;
        int min = Integer.MAX_VALUE;

        for(int i = 0; i < arr.length; i++) {
            min = Math.min(arr[i],min);
            max += arr[i];
        }

        boolean[] fly = new boolean[max+1];
        fly[0] = true;

        for(int i = 0; i < arr.length; i++) {
            for(int j = max; j >= arr[i]; j-- ) {
                fly[j] = fly[j - arr[i]] || fly[j];
            }
        }

        for(int i = min; i < fly.length; i++) {
            if(!fly[i]) {
                return i;
            }
        }

        return max+1;
    }
}
